package 剑指offer;

import java.util.*;

public class _32从上到下打印二叉树3 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    //上层从左向右访问，下一层从左向右入栈
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Stack<TreeNode> st = new Stack<>();
        Queue<TreeNode> q = new LinkedList<>();
        int dir = 1; // 1代表从左到右
        List<Integer> v = new ArrayList<>();
        st.push(root);
        while (!st.isEmpty()){
            int size = st.size(); //清空本层所有节点，将下层节点按照要求入栈，栈具有天然的逆序的能力
            for(int i = 0; i < size; i++){
                //之字形打印逻辑
                TreeNode curr = st.pop();
                v.add(curr.val);
                TreeNode first = (dir == 1) ? curr.left : curr.right;
                TreeNode second = (dir == 1) ? curr.right : curr.left;

                //层序遍历逻辑
                if(first != null){
                    q.offer(first);
                }
                if(second != null){
                    q.offer(second);
                }
            }
            result.add(new ArrayList(v));//一定要注意浅拷贝问题
            v.clear();
            while (!q.isEmpty()){
                st.push(q.poll());
            }

            dir = (dir == 1) ? 2 : 1;
        }
        return result;
    }
}
